//
//  main.m
//  SimpleAlgorithm
//
//  Created by lianglibao on 2019/3/16.
//  Copyright © 2019年 lianglibao. All rights reserved.
//

#import <Foundation/Foundation.h>
// 选择排序
void chooseSortArr(int *nums, int length) {
    for (int i = 0; i < length -1; i++) {
        for (int j = i+1; j < length ; j++) {
            if (nums[i]>nums[j]) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
    }
    for (int i = 0; i < length; i++) {
        printf("%d\n", nums[i]);
    }
}

// 冒泡排序
void bubbleSortArr(int *nums, int length) {
    for (int i=0; i<length-1; i++) {
        for (int j=0; j<length-1-i; j++) {
            if (nums[j]>nums[j+1]) {
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
    for (int i = 0; i < length; i++) {
        printf("%d\n", nums[i]);
    }
}

// 从一个有序数组中查找某个元素的位置下标
int findIndex(int *nums, int length, int key) {
    // 折半查找
    int min = 0;
    int max = length;
    int mid = (min + max)/2;
    int index = 0;
    while (nums[mid] != key) {
        if (nums[mid]>key) {
            max = mid - 1;
        } else if (nums[mid] < key) {
            min = mid + 1;
        }
        
        if (min > max) {
            index = -1;
            break;
        }
        mid = (min + max)/2;
    }
    if (index == 0) {
        index = mid;
    }
    
    printf("\n%d\n", index);
    return index;
}

// 插入个元素到一个有序数组中,求出插入位置下标
int insertIndex(int *nums,int key,int len){
    int min = 0;
    int max = len - 1;
    int index = 0;
    while(min <= max){
        int mid = (max + min)/2;
        if(nums[mid] > key){
            max = mid - 1;
        } else if(nums[mid] < key){
            min = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    printf("\n%d\n", index ?: min);
    return min;
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        //        int nums[] = {1, 11, 99, 22, 101, 88, 55};
        int nums[] = {99, 12, 88, 34, 5, 44, 12, 100};
        int len = sizeof(nums) / sizeof(nums[0]);
        // 冒泡排序
        bubbleSortArr(nums, len);
        // 从有序数组中查找某个元素位置
        findIndex(nums, len, 88);
        // 插入一个元素到有序数组中,插入位置
        insertIndex(nums, 13, len);
    }
    return 0;
}

